#include "evaluate.h"

extern int gridUnit;
extern int x_gridNum;
extern int y_gridNum;
extern int numBins;
extern ckt this_ckt;
extern double HPWL, penalty, displacement, max_displacement, targUt;
extern string directory;
extern vector<double> util_array;



/*-----------------------------------------------*/
/* Desc: A function to manipulate cells in a bin */
/*-----------------------------------------------*/

void bin_manipulation_1(ckt & ptrckt)
{
	ptrckt.tinyRows.clear();
	tinyRow_setup(ptrckt);

	//Perform manipulation_1
	for(int i = 0; i < numBins; i++)
	{
		global_move(ptrckt, i, 0.95, 0.85);
		intra_bin_optimization_1(ptrckt, i);
	}
}

/* This function takes an aggresive approach to reduce HPWL by
moving each movable cell to its optimal position in the bin.*/
void intra_bin_optimization_1(ckt & ptrckt, int binID)
{
	int row = 0;
	vector< pair<int,int> > node_list;
	
	// Preparation, add IDs of movable nodes into candidate list
	for(row = 0; row < 9; row++)
	{
		tinyRow & this_row = ptrckt.tinyRows[index_translate(binID, row)];
		if(this_row.isValid && this_row.NodeID.size() != 0)
		{
			//row_swap(ptrckt, this_row);
			row_optimization(ptrckt, this_row);
			for(int i = 0; i < this_row.NodeID.size(); i++)
			{
				if(!ptrckt.nodes[this_row.NodeID[i]].isFixed)
				{
					node_list.push_back(make_pair(row, this_row.NodeID[i]));
				}
			}
		}
	}
	if(node_list.size() == 0)
		return;

	// Perform manipulation to optimize wirelength
	vector< pair<int,int> >::iterator it;
	for(it = node_list.begin(); it != node_list.end(); ++it)
	{
		// Reference to the current node
		node & this_node = ptrckt.nodes[it->second];
		// Find the best position for the current node
		pair<int,int> pr = find_best_row(ptrckt, it->first, binID, this_node);
		// Reference to the source row
		tinyRow & src_row = ptrckt.tinyRows[index_translate(binID, it->first)];

		if(pr.first != it->first) // Move to another row
		{
			tinyRow & dest_row = ptrckt.tinyRows[index_translate(binID, pr.first)];
			if(insert2site(ptrckt, this_node, dest_row, pr.second))
				erase_src_node(ptrckt, src_row, this_node.ID);

			// Optimize node positions in the source row
			row_optimization(ptrckt, src_row);
			// Optimize node positions in the destination row
			row_optimization(ptrckt, dest_row);
		}
		else if(pr.first == it->first && pr.second != -1) // Move to another site at this row
		{
			erase_src_node(ptrckt, src_row, this_node.ID);
			insert2site(ptrckt, this_node, src_row, pr.second);

			// Optimize node positions in the source row
			row_optimization(ptrckt, src_row);
		}
	}
}


void bin_manipulation_2(ckt & ptrckt)
{
	ptrckt.tinyRows.clear();
	tinyRow_setup(ptrckt);

	//Perform manipulation
	for(int i = 0; i < numBins; i++)
	{
		intra_bin_optimization_2(ptrckt, i);
	}
}

void intra_bin_optimization_2(ckt & ptrckt, int binID)
{
	int row;
	for(row = 0; row < 9; row++)
	{
		tinyRow & this_row = ptrckt.tinyRows[index_translate(binID, row)];
		if(this_row.isValid && this_row.NodeID.size() != 0)
		{
			if(row != 8)
			{
				tinyRow & next_row = ptrckt.tinyRows[index_translate(binID, row + 1)];
				if(next_row.isValid)
				{
					vertical_optimization(ptrckt, this_row, next_row);
				}
			}
			row_optimization(ptrckt, this_row);
		}
	}

	for(row = 8; row >= 0; row--)
	{
		tinyRow & this_row = ptrckt.tinyRows[index_translate(binID, row)];
		if(this_row.isValid && this_row.NodeID.size() != 0)
		{
			if(row != 0)
			{
				tinyRow & next_row = ptrckt.tinyRows[index_translate(binID, row - 1)];
				if(next_row.isValid)
				{
					vertical_optimization(ptrckt, this_row, next_row);
				}
			}
			row_optimization(ptrckt, this_row);
		}
	}
}

bool vertical_optimization(ckt & ptrckt, tinyRow & this_row, tinyRow & dest_row)
{
	query answer;
	
	for(int i = 0; i < this_row.NodeID.size(); i++)
	{
		node & this_node = ptrckt.nodes[this_row.NodeID[i]];
		if(this_node.isFixed)
			continue;
		int x = this_node.x_coord;
		int y = this_node.y_coord;
		int best_x = -1;
		int best_reduction = 0;

		if(space_query(ptrckt, this_node, dest_row, 0, answer))
		{
			if(answer.available_space >= this_node.width)
			{
				int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx - x, dest_row.y - y);
				if(answer.space < this_node.width)
					reduction += this_node.width - answer.space;
				if(reduction < best_reduction)
				{
					best_reduction = reduction;
					best_x = 0;
				}
			}		
		}

		for(int j = 0; j < dest_row.NodeID.size(); j++)
		{
			int current_x = ptrckt.nodes[dest_row.NodeID[j]].x_coord + ptrckt.nodes[dest_row.NodeID[j]].width - dest_row.lx;
			
			if(space_query(ptrckt, this_node, dest_row, current_x, answer))
			{	
				if(answer.available_space >= this_node.width)
				{
					int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx + current_x - x, dest_row.y - y);
					if(answer.space < this_node.width)
						reduction += this_node.width - answer.space;
					if(reduction < best_reduction)
					{
						best_reduction = reduction;
						best_x = current_x;
					}
				}	
			}
		}

		if(best_x != -1)
		{
			erase_src_node(ptrckt, this_row, this_node.ID);
			insert2site(ptrckt, this_node, dest_row, best_x);
		}
	}
	return true;
}

/* Solve "fixed order linear programming problem". */
bool row_optimization(ckt & ptrckt, tinyRow & this_row)
{
	sort(this_row.NodeID.begin(), this_row.NodeID.end(), compareNodeID());
	if(this_row.NodeID.size() == 0 || this_row.isValid == false)
		return false;
	else if(this_row.NodeID.size() == 1)
	{
		node & this_node = ptrckt.nodes[this_row.NodeID[0]];
		if(this_node.isFixed)
			return false;
		else
		{
			// Move node in current tinyrow
			move_node_in_row(ptrckt, this_node, this_row.lx, this_row.rx - this_node.width, 2);
			// Updating the boundary information of current tinyrow
			fixRow(ptrckt, this_row);
			return true;
		}
	}
	else if(this_row.NodeID.size() >= 2)
	{
		if(this_row.NodeID.size() == 2)
		{
			node & node1 = ptrckt.nodes[this_row.NodeID[0]];
            node & node2 = ptrckt.nodes[this_row.NodeID[1]];
            if(!node1.isFixed && !node2.isFixed)
				bi_swap(ptrckt, this_row, 0);
		}
		else
		{
			for(int i = 0; i < this_row.NodeID.size() - 2; i++)
            {
                node & node1 = ptrckt.nodes[this_row.NodeID[i]];
                node & node2 = ptrckt.nodes[this_row.NodeID[i + 1]];
                node & node3 = ptrckt.nodes[this_row.NodeID[i + 2]];
                if(!node1.isFixed && !node2.isFixed && !node3.isFixed)
                {
                        tri_swap(ptrckt, this_row, i);
                }
                else if(node1.isFixed && !node2.isFixed && !node3.isFixed)
                {
                        bi_swap(ptrckt, this_row, i + 1);
                }
            }
        }

		bool all_movable = true;
		for(int i = 0; i < this_row.NodeID.size(); i++)
		{
			if(ptrckt.nodes[this_row.NodeID[i]].isFixed)
			{
				all_movable = false;
				break;
			}
		}
		
		if(all_movable)
		{
			set<int> related_nets;
			vector<pin>::iterator it;
			for(int i = 0; i < this_row.NodeID.size(); i++)
			{
				node & cur_node = ptrckt.nodes[this_row.NodeID[i]];
				for(it = cur_node.pins.begin(); it != cur_node.pins.end(); ++it)
					related_nets.insert(it->pin2net);	
			}
			//int hpwl1 = calculate_local_HPWL(ptrckt, related_nets);
			place_tinyRow_DP(ptrckt, this_row);
			//int hpwl2 = calculate_local_HPWL(ptrckt, related_nets);
			// if(hpwl2 > hpwl1)
			// 	cout << "Weird " << hpwl2 - hpwl1 << endl;
			fixRow(ptrckt, this_row);
			return true;
		}
	}
	return false;
}



/* Given a cell, find the best position inside a bin */
pair<int,int> find_best_row(ckt & ptrckt, int src_row, int binID, node & this_node)
{
	assert(!this_node.isFixed);
	int best_row = src_row;
	int best_reduction = -9;
	int best_x = -1;
	int row = 0;
	int x = this_node.x_coord;
	int y = this_node.y_coord;
	query answer;

	for(row = 0; row < 9; row++)
	{
		if(row == src_row)
		{
			tinyRow & src_row = ptrckt.tinyRows[index_translate(binID, row)];
			int order = 0;
			for(order = 0; order < src_row.NodeID.size(); order++)
			{
				if(src_row.NodeID[order] == this_node.ID)
					break;
			}
			if(order > 1)
			{
				if(space_query(ptrckt, this_node, src_row, 0, answer))
				{
					if(answer.available_space >= this_node.width)
					{
						int reduction = delta_HPWL(ptrckt, this_node.ID, src_row.lx - x, 0);
						if(answer.space < this_node.width)
							reduction += this_node.width - answer.space;
						if(reduction < best_reduction)
						{
							best_reduction = reduction;
							best_x = 0;
							best_row = row;
						}
					}		
				}
			}
			for(int i = 0; i < src_row.NodeID.size(); i++)
			{
				if(i == order || i == order - 1)
					continue;
				int current_x = ptrckt.nodes[src_row.NodeID[i]].x_coord + ptrckt.nodes[src_row.NodeID[i]].width - src_row.lx;
				
				if(space_query(ptrckt, this_node, src_row, current_x, answer))
				{	
					if(answer.available_space >= this_node.width)
					{
						int reduction = delta_HPWL(ptrckt, this_node.ID, src_row.lx + current_x - x, 0);
						if(answer.space < this_node.width)
							reduction += this_node.width - answer.space;
						if(reduction < best_reduction)
						{
							best_reduction = reduction;
							best_x = current_x;
							best_row = row;
						}
					}	
				}
			}
		}
		else
		{
			tinyRow & dest_row = ptrckt.tinyRows[index_translate(binID, row)];
			if(!dest_row.isValid)
				continue;

			if(space_query(ptrckt, this_node, dest_row, 0, answer))
			{
				if(answer.available_space >= this_node.width)
				{
					int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx - x, dest_row.y - y);
					if(answer.space < this_node.width)
						reduction += this_node.width - answer.space;
					if(reduction < best_reduction)
					{
						best_reduction = reduction;
						best_x = 0;
						best_row = row;
					}
				}		
			}

			for(int i = 0; i < dest_row.NodeID.size(); i++)
			{
				int current_x = ptrckt.nodes[dest_row.NodeID[i]].x_coord + ptrckt.nodes[dest_row.NodeID[i]].width - dest_row.lx;
				
				if(space_query(ptrckt, this_node, dest_row, current_x, answer))
				{	
					if(answer.available_space >= this_node.width)
					{
						int reduction = delta_HPWL(ptrckt, this_node.ID, dest_row.lx + current_x - x, dest_row.y - y);
						if(answer.space < this_node.width)
							reduction += this_node.width - answer.space;
						if(reduction < best_reduction)
						{
							best_reduction = reduction;
							best_x = current_x;
							best_row = row;
						}
					}	
				}
			}
		}
		
	}
	return make_pair(best_row, best_x);
}


